#pragma once

#include <array>
#include <string>
#include <utility>
#include <vector>

namespace solution_005
{

class Solution {
public:
    std::string longestPalindrome(std::string s)
    {
        int n = s.size();
        std::array< std::vector<int>, 2 > palindrome;

        /* len == 1, step = 0 */
        int max_step = 0;
        for (int i = 0; i < n; ++i)
            palindrome.at(0).push_back(i);

        /* len == 2, step = 1 */
        palindrome.at(1).resize(n, 0);
        for (int i = 0; i + 1 < n; ++i) {
            if (s.at(i) == s.at(i + 1)) {
                palindrome.at(1).at(i) = i + 1;
                ++palindrome.at(1).back();
            }
        }
        if (palindrome.at(1).back() > 0)
            max_step = 1;

        for (int step = 2; step < n; ++step) {
            auto& palin = palindrome.at(step % 2);
            palin.back() = 0;
            for (int i = 0; i < n - step; ++i) {
                if ( palin.at(i + 1) == i + step - 1 && s.at(i) == s.at(i + step) ) {
                    palin.at(i) = i + step;
                    ++palin.back();
                }
            }
            if (palin.back() > 0)
                max_step = step;
            if (palindrome.at(0).back() == 0 && palindrome.at(1).back() == 0)
                break;
        }

        auto& palin = palindrome.at(max_step % 2);
        for (int i = 0; i + 1 < n; ++i) {
            if (palin.at(i) - i == max_step)
                return s.substr(i, max_step + 1);
        }
        return s;
    }

    std::string longestPalindrome2(std::string s)
    {
        int l = 0;
        int r = 0;
        int max = 1;
        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            auto [l1, r1] = expand(s, i, i);
            auto [l2, r2] = expand(s, i, i + 1);
            int len1 = r1 - l1 + 1;
            int len2 = r2 - l2 + 1;
            if (len1 > max) max = len1, l = l1, r = r1;
            if (len2 > max) max = len2, l = l2, r = r2;
        }
        return s.substr(l, max);
    }

private:
    std::pair<int, int> expand(const std::string& s, int l, int r)
    {
        while (l >= 0 && r < (int)s.size() && s.at(l) == s.at(r))
            --l, ++r;
        return {++l, --r};
    }
};

}  /* namespace solution_005 */
